#include<vector>
#include<iterator>
#include<iostream>
using namespace std;

struct PolyNode
{
    PolyNode(int coef, int expn)
    : m_nCoef(coef)
    , m_nExpn(expn)
    {
    }
    
    int m_nCoef;
    int m_nExpn;
};

class CPolyn : public vector<PolyNode>
{
    friend ostream& operator<<(ostream& os, CPolyn const& polyn);
public:
    void AddItem(PolyNode const& node);
    CPolyn operator+(CPolyn const& one);
};

void CPolyn::AddItem(PolyNode const& node)
{
    push_back(node);
}

CPolyn CPolyn::operator+(CPolyn const& one)
{
    CPolyn res;
    vector<PolyNode>::const_iterator itOne, it;
    vector<PolyNode>::const_iterator itOneEnd = one.end();
    vector<PolyNode>::const_iterator itEnd = end();
    
    for (itOne = one.begin(), it = begin();
        itOne != itEnd && it != itEnd; )
    {
        if (it->m_nExpn < itOne->m_nExpn)
        {
            res.push_back(*it);
            ++it;
        }
        else if(it->m_nExpn > itOne->m_nExpn)
        {
            res.push_back(*itOne);
            ++itOne;
        }
        else
        {
            int nCoef = itOne->m_nCoef + it->m_nCoef;
            if (nCoef != 0)
            {
                res.push_back(PolyNode(nCoef, it->m_nExpn));
            }
            
            ++it;
            ++itOne;
        }
    }
    if (it != itEnd)
    {
        res.insert(res.end(), it, itEnd);
    }
    else if(itOne != itOneEnd)
    {
        res.insert(res.end(), itOne, itOneEnd);
    }
    
    return res;
}

ostream& operator<<(ostream& os, CPolyn const& polyn)
{
    vector<PolyNode>::const_iterator it, itEnd = polyn.end();
    
    for (it = polyn.begin(); it != itEnd; ++it)
    {
        if (0 == it->m_nExpn)
        {
            os<< it->m_nCoef;
        }
        else
        {
            os<< it->m_nCoef << "X^" << it->m_nExpn;
        }
        os<< " ";
    }
    os<<"\n";
    
    return os;
}

int main(void)
{
    CPolyn poOne, poTwo;
    poOne.AddItem(PolyNode(5, 0));
    poOne.AddItem(PolyNode(4, 1));
    poOne.AddItem(PolyNode(-2, 2));
    poOne.AddItem(PolyNode(7, 4));
    
    poTwo.AddItem(PolyNode(6, 1));
    poTwo.AddItem(PolyNode(2, 2));
    poTwo.AddItem(PolyNode(4, 3));
    poTwo.AddItem(PolyNode(8, 6));
    
    CPolyn poThree = poOne + poTwo;
    
    cout<< poOne;
    cout<< poTwo;
    cout<< poThree;
    
    system("pause");
}
